package com.example.javamaday.sort;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {

    /**
     * 归并所需的辅助数组
     */
    private static Comparable[] assist;

    public static void main(String[] args) {
        Integer[] arr = {4, 5, 3, 9, 2, 1};
        sort(arr);
        System.out.println(Arrays.asList(arr).toString());
    }

    public static void sort(Comparable[] a) {
        // 定义一个辅助数组
        assist = new Comparable[a.length];
        // 定义lo遍历和hi变量，分别记录数组中最小的索引和最大的索引
        int lo = 0;
        int hi = a.length - 1;
        sort(a, lo, hi);
    }

    public static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        // 对lo和hi之间的数据进行分组，分别对每一组数据进行排序，再把两组中的数据进行归并
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid);
        sort(a, mid + 1, hi);

        merge(a, lo, mid, hi);
    }

    // 对数据进行归并
    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        // 定义三个指针
        int i = lo;
        int p1 = lo;
        int p2 = mid + 1;
        // 遍历，移动p1和p2指针，比较对应索引处的值，找出最小的，放到辅助数组的对应索引处
        while (p1 <= mid && p2 <= hi) {
            if (less(a[p1], a[p2])) {
                assist[i++] = a[p1++];
            } else {
                assist[i++] = a[p2++];
            }
        }
        // 遍历，如果p1的指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引
        while (p1 <= mid) {
            assist[i++] = a[p1++];
        }
        // 遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引
        while (p2 <= hi) {
            assist[i++] = a[p2++];
        }
        // 把辅助数组中的元素拷贝到原数组中
        for (int index = lo; index <= hi; index++) {
            a[index] = assist[index];
        }
    }

    private static boolean less(Comparable i, Comparable j) {
        return i.compareTo(j) < 0;
    }

}
